﻿// https://newcoder.com
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//例：图中给定树{ 3,5,1,6,2,0,8,#,#,7,4 } 中，节点6、节点4的最近公共祖先为5。


//TreeNode* nearestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//    if (root == nullptr) return nullptr;
//    if (root->val == p->val || root->val == q->val)
//        return root;
//
//    TreeNode* left = nearestCommonAncestor(root->left, p, q);
//    TreeNode* right = nearestCommonAncestor(root->right, p, q);
//    if (left != nullptr && right != nullptr)
//        return root;
//    return left != nullptr ? left : right;
//}

